package com.bee.剑指offer;

import java.util.Arrays;

/**
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。
 * 例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
 */
public class 丑数 {

    /**
     * 暴力破解有问题
     * @param index
     * @return
     */
    public static int GetUglyNumber_Solution(int index) {
        int count = 1;
        int flag = 0;
        while (true) {
            if(check(count)) {
                flag++;
            }
            if(flag == index) {
                return count;
            }
            count++;
        }
    }

    public static boolean check(int index) {
        while (index % 2 == 0) {
            index /= 2;
        }
        while (index % 3 == 0) {
            index /= 3;
        }
        while (index % 5 == 0) {
            index /= 5;
        }
        return index == 1;
    }

    public static int GetUglyNumber_Solution2(int index) {
        if(index <= 6){
            return index;
        }
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        int[] res = new int[index];
        res[0] = 1;
        for (int i = 1; i < index; i++) {
            res[i] = Math.min(res[i2]*2,Math.min(res[i3]*3,res[i5]*5));
            if (res[i2]*2 == res[i]) {
                i2++;
            }
            if (res[i3]*3 == res[i]) {
                i3++;
            }
            if (res[i5]*5 == res[i]) {
                i5++;
            }
        }
        System.out.println(Arrays.toString(res));
        return res[index - 1];
    }

    public static void main(String[] args) {
        System.out.println(GetUglyNumber_Solution2(7));
    }
}
